package leetcode.动态规划;

public class Leetcode1049 {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum = sum + stones[i];
        }
        int targrt = sum/2;
        int[] dp = new int[targrt+1];
        for (int i = 0; i < stones.length; i++) {
            for(int j = targrt;j>=stones[i];j--){
                dp[j] = Math.max(dp[j-stones[i]]+stones[i],dp[j]);//装或者不装
            }
        }
        return sum - 2*dp[targrt];
    }

    public int lastStoneWeightII1(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum = sum + stones[i];
        }
        int targrt = sum/2;
        int[][] dp = new int[stones.length+1][targrt+1];
        for (int i = 1; i <= stones.length; i++) {
            for(int j = 0;j<=targrt;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=stones[i-1]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        }
        return sum - 2*dp[stones.length][targrt];
    }
}
